package tools;

import java.util.List;

import Triangulation.oldMinimalityMetrics.OldMinimalityMetric;
import datatypes.Edge;
import datatypes.IndexedFaceSet;
import datatypes.Vertex;
import datatypes.list.DoublyLinkedList;

/**
 * 
 * @author markessien, nils
 *
 */
public class OldLMTSkeletonCreator {
	
	class Logger {
		long edgesCheckedForIntersection = 0;
		int edgesWithoutLocalMinimum = 0;
		int nonIntersectingEdges = 0;
		double time;
		double timePartA = 0;
		double timePartB = 0;
		double convexHullTime = 0;
		double timeRemoveNonEmptyTriangles = 0;
	}
	
	private Logger logger = new Logger();

	static private LMTStatistics stats = new LMTStatistics();
	private static int edgesChecked = 0;
	private OldMinimalityMetric metric;
	
	public OldLMTSkeletonCreator(OldMinimalityMetric metric) {
		this.metric = metric;
	}

	
	/**
	 * The LMT-skeleton is a subgraph of the original graph. It contains all the
	 * edges that are in all possible minimum weight triangulations. After the LMT
     * is found, then the MWT can be calculated
	 * SEE A Large Subgraph of the Minimum Weight Triangulation page294
	 * 
	 * This function calculates the LMT.
	 * 
	 * 
	 * @param points The set of points
	 * @return The list with all edges within the skeleton in them
	 */
	public List<Edge> calculateLMT(IndexedFaceSet set) {
		long start = System.currentTimeMillis();
		
		set.generateEdges();
		if (set.size() <= 3) {
			return set.getCandidateEdges();
		}
		boolean edgeChanged = false;
		
		log("allVerticesCount", set.size());
		log("allEdgeCount", set.getCandidateEdges().size());
		
		long startTris = System.currentTimeMillis();
		set.generateTriangles();
//		set.removeNonEmptyTriangles();
		logger.timeRemoveNonEmptyTriangles += ((double)(System.currentTimeMillis() - startTris))/1000;
		
		// This method will look at the list of all potential edges ( set.getEdges() )
		// and it will add all edges that belong to the convex hull to the edgesIn list.
		// The convex hull is always part of any triangulation, and thus its edges are
		// in any minimum triangulation.
		List<Vertex> convexHullPoints = ConvexHullCreator.doJarvisMarch(set);
		
		// edgesIn is a list of edges that have been determined to be in
		// any locally minimal triangulation
		List<Edge> edgesIn = ConvexHullCreator.getHullEdges(convexHullPoints, set.getCandidateEdges()); // TODO: may be inefficient...
		
		log("hullEdgeCount", edgesIn.size());
		
		// Remove convex hull edges from our candidate list
		for (Edge e:edgesIn) {
			set.removeEdgeButLeaveTriangles(e);
		}
		
//		set.removeNonEmptyTriangles();
		
		int edgesWithoutLocalMinimum = 0;
		int nonIntersectingEdges = 0;
		DoublyLinkedList<Edge> edges = set.getCandidateEdges();
		do {
			edgeChanged = false; // for now
			
//			System.out.println("*** Part (a) *** (" + set.numberOfTriangles() + " tris)");
			long startA = System.currentTimeMillis();
			for (Edge edge : edges) {
				set.removeNonEmptyTrianglesForEdge(edge);
				if ( ! edge.isDiagonalOfQuadrilateral() ) {
					continue;
				}
				
				// If we find that this edge is not the local minimum for any possible
				// quadrilateral, this edge cannot be an element of an MWT. Hence we can
				// remove it from the candidates.
				if ( ! metric.localMinimumExistsForEdge(edge, set) ) {
					set.removeEdge(edge);
					edgeChanged = true;
					edgesWithoutLocalMinimum++;
				} else {
					edge.setHighlighted(true);
				}
		    } // for (Edge e)	
			logger.timePartA += ((double)(System.currentTimeMillis() - startA))/1000;
//			System.out.println("*** Part (b) ***");
			long startB = System.currentTimeMillis();
			for (Edge edge : edges) {
				
				// IF e intersects no other edge in candEdges THEN add e to the edgesIn
				boolean intersects = false;
				for (Edge otherEdge: set.getCandidateEdges()) {
					edgesChecked++;
					
					if ( ! edge.isAdjacentToEdge(otherEdge)) {
						// Using negative precision value to prevent adjacent edges
						// from being detected as intersecting edges
						if (edge != otherEdge && edge.intersects(otherEdge, -0.00001)) {
							intersects = true;
							break;
						}
					}
				}
				
				if (intersects == false) {
//					if (edgesIn.indexOf(edge) == -1) {	// TODO: do we really need to check whether edge already exists???
						edgesIn.add(edge);
						set.removeEdgeButLeaveTriangles(edge); // remove edge from candEdges. Not specified in the paper
						edgeChanged = true;
						nonIntersectingEdges++;
//					}
				}
			}
			logger.timePartB += ((double)(System.currentTimeMillis() - startB))/1000;
		} while (edgeChanged);
		logger.time = ((double)(System.currentTimeMillis() - start))/1000;
		
		log("edgesWithoutLocalMinimum", edgesWithoutLocalMinimum);
		log("nonIntersectingEdges", nonIntersectingEdges);
		log("edgesChecked ", edgesChecked);
		log("old LMT Algorithm Complete");
		System.out.println("Running time: " + logger.time);
		System.out.println("Running time part A: " + logger.timePartA);
		System.out.println("Running time part B: " + logger.timePartB);
		System.out.println("");
		edgesChecked = 0;
		logger = new Logger();
		
//		System.out.println("\n***\n  found " + edgesIn.size() + " edges!\n***\n");
		return edgesIn;
	}

	private static void log(String key) {
		stats.log(key, null);
	}
	
	private static void log(String key, Integer val) {
		stats.log(key, val.toString());
	}
	
	public String getMetricName() {
		return metric.getName();
	}
}
